package BSTOperationsPack;

public class BSTOperations {

    // 1. Insert a value into BST
    public TreeNodePack.TreeNode insertIntoBST(TreeNodePack.TreeNode root, int val) {
        if (root == null) return new TreeNodePack.TreeNode(val);
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        }
        return root; // 如果值已存在，不插入（假设BST不允许重复）
    }

    // 2. Validate if a binary tree is a BST
    public boolean isValidBST(TreeNodePack.TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNodePack.TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }

    // 3. Delete a node from BST
    public TreeNodePack.TreeNode deleteNode(TreeNodePack.TreeNode root, int key) {
        if (root == null) return null;
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            // 找到要删除的节点
            if (root.left == null) return root.right;   // 只有一个右子节点
            if (root.right == null) return root.left;  // 只有一个左子节点
            // 有两个子节点：找到右子树的最小节点替换
            TreeNodePack.TreeNode minNode = findMin(root.right);
            root.val = minNode.val; // 替换值
            root.right = deleteNode(root.right, minNode.val); // 删除右子树的最小节点
        }
        return root;
    }

    private TreeNodePack.TreeNode findMin(TreeNodePack.TreeNode node) {
        while (node.left != null) node = node.left;
        return node;
    }

    // 测试代码示例
    public static void main(String[] args) {
        BSTOperations ops = new BSTOperations();

        // 插入测试
        TreeNodePack.TreeNode root = null;
        root = ops.insertIntoBST(root, 5);
        root = ops.insertIntoBST(root, 3);
        root = ops.insertIntoBST(root, 7);
        System.out.println("Is valid BST after insertion? " + ops.isValidBST(root)); // true

        // 删除测试
        root = ops.deleteNode(root, 3);
        System.out.println("Is valid BST after deletion? " + ops.isValidBST(root)); // true
    }
}